package _interview75;

import java.util.Arrays;

/**
 * 746. 使用最小花费爬楼梯
 */
public class No746 {
    private int[] cost;
    private int[] cache;

    public int minCostClimbingStairs(int[] cost) {
        this.cost = cost;
        int n = cost.length;
        cache = new int[n + 1];
        Arrays.fill(cache, -1);
        return Math.min(dfs(0), dfs(1));
    }

    private int dfs(int i) {
        if (i >= cost.length) return 0;
        else if (cache[i] != -1) return cache[i];
        else return cache[i] = Math.min(dfs(i + 1) + cost[i], dfs(i + 2) + cost[i]);
    }
}
